package leetcode.d28;

//hello
//ll
public class Solution {

    public static void main(String[] args) {
        String a = "mississippi";
        String b = "issipi";
        System.out.println(strStr(a, b));
    }

    public static int strStr(String haystack, String needle) {
        char[] main = haystack.toCharArray();
        char[] chars = needle.toCharArray();
        if (chars.length == 0){
            return 0;
        }
        if (chars.length>main.length){
            return -1;
        }
        int[] next = new int[chars.length];
        int j = 0;
        next[0] = j;
        for (int i = 1; i < chars.length; i++) {
            while (chars[i] != chars[j] && j >= 1) {
                j = next[j - 1];
            }
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i] = j;

        }
        int index = 0;
        int p = 0;
        while (index < main.length) {
            while (main[index] == chars[p]) {
                p++;
                index++;
                if (p==chars.length){
                    return index-chars.length;
                }
                if (index==main.length){
                    return -1;
                }
            }
            if (p == 0) {
               index++;
            }
            else{
                p = next[p - 1];
            }
        }
        return -1;
    }
}
